# from math import prod
from typing import List


def prod(iterable):
    res = 1
    for x in iterable:
        if x == 0:
            return 0
        res *= x
    return res


class Solution:
    def countSubgraphsForEachDiameter(self, n_nodes: int, edges: List[List[int]]) -> List[int]:
        edges = [(u-1, v-1) for u,v in edges]

        adj = [[] for _ in range(n_nodes)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        dp_cache = [[[None for _ in range(n_nodes)] for _ in range(n_nodes)] for _ in range(n_nodes)]

        def dp(a, b, n):
            """ 从A往B扩展的深度小于等于n的树的数量 """
            if dp_cache[a][b][n] is not None:
                return dp_cache[a][b][n]
            if n == 0:
                count = 1
            elif n == 1:
                count = 2
            else:
                count = 1 + prod(dp(b, C, n - 1) for C in adj[b] if C != a)
            dp_cache[a][b][n] = count
            return count

        def f(a, b, n):
            """ 从A往B扩展的深度等于n的树的数量 """
            if n == 0:
                return 1
            return dp(a, b, n) - dp(a, b, n - 1)

        def g(a, n):
            """ 以A为中心扩展出的长度为2n的树的数量 """
            term0 = prod(dp(a, b, n) for b in adj[a])
            term1 = prod(dp(a, b, n - 1) for b in adj[a])
            term2 = sum(f(a, b, n) * term1 // dp(a, b, n - 1) for b in adj[a])
            return term0 - term1 - term2

        def h(a, b, n):
            """ 以边AB为中心扩展出的长度为2n+1的树的数量 """
            return f(a, b, n + 1) * f(b, a, n + 1)

        result = []
        for d in range(1, n_nodes):
            if d % 2 == 1:
                result.append(sum(h(a, b, (d-1) // 2) for a, b in edges))
            else:
                result.append(sum(g(a, d//2) for a in range(n_nodes)))
        return result


n = 4
edges = [[1,2],[2,3],[2,4]]
res = Solution().countSubgraphsForEachDiameter(n, edges)
print(res)

n = 2
edges = [[1,2]]
res = Solution().countSubgraphsForEachDiameter(n, edges)
print(res)


n = 3
edges = [[1,2],[2,3]]
res = Solution().countSubgraphsForEachDiameter(n, edges)
print(res)


